<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>86. 分隔链表</title>
  </head>
  <body>
    <script>
      //     给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

      // 你应当 保留 两个分区中每个节点的初始相对位置。

      // 来源：力扣（LeetCode）

      // 输入：head = [1,4,3,2,5,2], x = 3
      // 输出：[1,2,2,4,3,5]
      // 示例 2：

      // 输入：head = [2,1], x = 2
      // 输出：[1,2]

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/partition-list
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

      /**
       * Definition for singly-linked list.
       * function ListNode(val, next) {
       *     this.val = (val===undefined ? 0 : val)
       *     this.next = (next===undefined ? null : next)
       * }
       */

      function ListNode(val, next) {
        this.val = val === undefined ? 0 : val
        this.next = next === undefined ? null : next
      }

      /**
       * @param {ListNode} head
       * @param {number} x
       * @return {ListNode}
       */
      var partition = function (head, x) {
        let newHead = null // 创建新链表，保存要移除的节点
        let keepNewHead = null // 保存新链表的头节点
        let preNode = head // 保存符合节点的上一节点
        let node = head // 保存符合条件的节点
        let now = head // 当前指向的节点
        let preNow = head // 当前指向节点的上一节点
        let isFind = false // 是否找到符合条件节点
        let isSelect = false // 是否已经创建新链表
        while (now) {
          // 遍历链表
          if (now.val >= x && !isFind) {
            // 找到符合条件节点
            node = now
            preNode = preNow
            isFind = true
          }
          if (now.val < x && isFind) {
            // 寻找要移动的节点
            if (!isSelect) {
              // 创建新链表
              newHead = new ListNode(now.val)
              keepNewHead = newHead
              isSelect = true
            } else {
              // 新链表已经创建
              newHead.next = new ListNode(now.val)
              newHead = newHead.next
            }
            preNow.next = now.next
            now = preNow
          }
          preNow = now
          now = now.next
        }
        // debugger
        if (keepNewHead) {
          // 存在移动节点
          if (head === preNode && head === node) {
            // 符合节点为头指针
            newHead.next = node
            return keepNewHead
          }
          // 符合节点为链表中间
          preNode.next = keepNewHead
          newHead.next = node
        }
        return head
      }

      const head = new ListNode(1)
      const sec = new ListNode(4)
      const a = new ListNode(3)
      const b = new ListNode(2)
      const c = new ListNode(5)
      const d = new ListNode(2)
      head.next = sec
      sec.next = a
      a.next = b
      b.next = c
      c.next = d
      console.log(partition(head, 3))
    </script>
  </body>
</html>
